/****************************************************************************
CX Postfix Generator - Machine Problem 1 - CS32 
Reads infix statements from a text file and generates the equivalent Postfix
  expressions, as well as determines whether they are well-formed or not

Implements the Shunting-yard algorithm as detailed on Wikipedia
(http://en.wikipedia.org/wiki/Shunting-yard_algorithm)
and as described by its inventor, Edsger Dijkstra
(originally in this paper: http://www.cs.utexas.edu/~EWD/MCReps/MR35.PDF)

Compiled with GCC; Tested on Windows 8.1

Vincent Paul F. Fiestada - 201369155 - vffiestada@upd.edu.ph
*****************************************************************************/

#include "cardinal.h" // Note: 'cardinal.h' has the non-standard preprocessor directive #pragma once
#include "stack.h"

#define STRINGMAX 100
#define INPUTFILENAME "infix.txt"

// Error code constants
#define ERR_INPUTFILE_CANNOTOPEN 100
#define ERR_INPUTFILE_CORRUPT_LINE1 101
#define ERR_INPUTFILE_CORRUPT_LINES 102

// Function declarations; see below for definitions
char * mfgets(char * saveto, float length, FILE * source);
char * smallcaps (char * fc);
char * reversepolish(char * dest, char * src);
int tokenpriority(char token);
bool findrank(char *str);

int main()
{	
	printf("\n=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+\n");
	printf("       CX Postfix Generator || CS 32 Machine Problem 1\n");
	printf("Vincent Paul F. Fiestada | 201369155 | vffiestada@upd.edu.ph\n");
	printf("=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+\n\n");

	// Create stack and initialize variables
	FILE * inputFile;
	char tempstring[100];
	char * tempchar;
	int numberOfInputs = 0;
	int i = 0;
	bool isValid; // will hold a value that will determine whether the infix expression was invalid

	inputFile = fopen(INPUTFILENAME, "r");	// open input file
	// Check for error in opening file stream
	if (inputFile==NULL)
	{ 		
		// If inputFile is null, then the stream couldn't be opened
		// report error
		fprintf(stderr,"\nFATAL ERROR!\nFailed to open '%s'. ",INPUTFILENAME);
		exit(ERR_INPUTFILE_CANNOTOPEN); // exit with appropriate error code
	}
	tempchar = mfgets(tempstring, STRINGMAX, inputFile); // Read the first line
	if (tempchar == NULL) // If first line is empty, report an error
	{
		fprintf(stderr,"\nFATAL ERROR!\nCould not read line 1 of the input file '%s'.",INPUTFILENAME);
		exit(ERR_INPUTFILE_CORRUPT_LINE1);
	}
	numberOfInputs = atoi(tempchar); // The first line should be an integer
									 // It should be a count of how many infix expressions follow
									 // If line 1 is not a proper integer, atoi will return 0

	// Create arrays of strings for the inputs and outputs
	// This has to be done here when we already know the numberOfInputs
	char inputs[numberOfInputs][STRINGMAX];
	char outputs[numberOfInputs][STRINGMAX]; // Just in case more features are added later, retain all output

	// Read each input string and store it
	for (i = 0; i < numberOfInputs && tempchar != NULL; i++)
	{
		// NOTE: mfgets will read the string and will also handle
		//       the removal of trailing and leading whitespaces (' ','\t','\n')
		//       and convert the strings into smallcaps
		tempchar = mfgets(tempstring, STRINGMAX, inputFile);
		if (tempchar == NULL) // Take care of errors in reading the file
		{
			fprintf(stderr,"\nFATAL ERROR!\nSome data from the input file '%s' is missing at line %d.",INPUTFILENAME, i+2);
			exit(ERR_INPUTFILE_CORRUPT_LINES);
		}
		// If no errors, copy string into input array
		strcpy(&(inputs[i][0]), tempchar);
	}
	// Print the initial input infix expressions
	printf("Read %d input strings:",numberOfInputs);
	for(i = 0; i < numberOfInputs; i++)
	{
		printf("\n%d - %s",i,inputs[i]);
	}

	fclose(inputFile); // close input file

	// Convert each input and store into output, then print
	printf("\nInfix to Postfix Conversion Results:");
	for (i = 0; i < numberOfInputs; i++)
	{
		// Convert each string in inputs and print out the outputs
		isValid = true;
		outputs[i][0] = '\0'; // Initialize output string as an empty string, otherwise strcat breaks
		isValid = (bool)reversepolish(outputs[i], inputs[i]); // if NULL is returned, isValid is false
		// Print output and/or error message if invalid/not well-formed
		printf("\n%d - %s",i,outputs[i]);
		// The expression (infix & postfix) is not well-formed if FINDRANK returns false
		if (findrank(outputs[i]) == false && isValid == true)
		{
			printf(" ... NOT WELL-FORMED");
		}
	}

	return 0; // Return no errors; terminate
}

//<summary>
// mfgets - Modified fgets - reads string from a FILE stream, cleans up the string
//        and returns pointer to the stored string
//</summary>
char * mfgets(char * saveto, float length, FILE * source){
	char * trim;
	// mfgets(...) returns pointer to saveto
	//  after reading string into it.
	saveto = fgets(saveto, length, source);
	// Check for Error in reading string from stream
	if(saveto==NULL){
		return NULL;
	}
	// Trim the string for whitespaces
	// First, look for leading newlines, tabs, and spaces
	trim = saveto;
	while(*trim != '\0' && (*trim == '\n' || *trim == '\t' || *trim == ' '))
	{
		saveto++; // Move string pointer to the next one (discard previous whitespace)
		trim++;
	}
	// Second, look for trailing whitespace
	trim = saveto + strlen(saveto) - 1;; // Start with the last char (before the terminating null)
	while(*trim == '\n' || *trim == '\t' || *trim == ' ')
	{
		*trim = '\0'; // Replace with terminating null
		trim--;
	}
	saveto = smallcaps(saveto);
	return saveto;
}

//<summary>
// smallcaps - converts a string into all small caps
//</summary>
char * smallcaps (char * fc){
	char * curr_letter = fc;
	while(*curr_letter!='\0'){
		if(*curr_letter>=65&&*curr_letter<=90){
			*curr_letter += 32;		//Make small-caps
		}
		curr_letter++;
	}
	return fc;
}

//<summary>
// reversepolish - converts an infix expression to a postfix expression
//                  takes as arguments a pointer to the source string and
//					a pointer to the destination string
//				  - returns either a pointer to the destination string; or,
//                - if an error is encountered, the error message is written to the destination string
//                - and NULL is returned
//														* 	*	*
//                - An Implementation of the Shunting-yard algorithm (Dr. Edsger Dijkstra, 1961)
//					and described in this Wikipedia article: http://en.wikipedia.org/wiki/Shunting-yard_algorithm
//					and illustrated here: 
//					http://upload.wikimedia.org/wikipedia/commons/thumb/2/24/Shunting_yard.svg/400px-Shunting_yard.svg.png
// 					which was the simplest way to convert infix to postfix, with time complexity of O(n)
//				 	Although empirical complexity might be higher because of all the conditions and strcat calls
//</summary>
char * reversepolish(char * dest, char * src)
{
	char * c = src;
	char tempstr[] = {' ','\0'}; // For concatenating into the output
 	int cpriority = 0; // Current token's priority
	int opriority = 0; // priority of operator from top of Stack
	Stack * operatorStack = CreateNewStack(); // Operator Stack
	char tempchar;

	do // Keep reading source string while a null terminator has not been encountered yet
	{	

		/*************************** IMPORTANT STUFF *************************
		The order of the if-else branches in this code block, as well as
		whether c is incremented in each branch is important for the conversion
		to work properly and for errors to be properly identified and handled
		*********************************************************************/

		cpriority = tokenpriority(*c);
		// Check for invalid tokens
		// A token is invalid if it is not one of the operators and not alpha-numeric
		if (cpriority == 0 && !(isalnum(*c)))
		{
			char tempstr2[] = "Invalid Expression; Token not recognized.";
			strcpy(dest, tempstr2);
			AnnihilateStack(operatorStack);
			return NULL;
		}
		// Check of whitespace in between tokens (tokenproirity returns -1 for ' ' and '\t')
		else if (cpriority < 0)
		{
			char tempstr2[] = "Invalid Expression; Whitespace inside expression.";
			strcpy(dest, tempstr2);
			AnnihilateStack(operatorStack);
			return NULL;
		}
		else if (cpriority == 0)
		{
			// If token is an operand (alpha-numberic character, concatenate into output)
			tempstr[0] = *c;
			strcat(dest, tempstr);
			c++; // and move on to next token
		}
		else if (cpriority == 1)
		{
			// If token is opening parenthesis, push to stack and
			PushToStack(operatorStack, *c);
			c++; // move on to next token
		}
		else if (cpriority == 2)
		{
			// If token is closing parenthesis,
			do
			{
				// pop stack into the output and repeat
				// until the an opening parenthesis is found
				if (operatorStack->Top == NULL)
				{
					// If stack is empty before a '(' is encountered,
					// That means that a '(' is missing
					// Report error and end
					char tempstr2[] = "Invalid Expression; Missing at least one '(' parenthesis.";
					strcpy(dest, tempstr2);
					AnnihilateStack(operatorStack);
					return NULL;
				}
				tempchar = PopFromStack(operatorStack); // pop from stack
				if (tempchar != '(')
				{
					// Opening parentheses need not be appended to the output string
					// Otherwise, append token to the output and compare again.
					tempstr[0] = tempchar;
					strcat(dest, tempstr);
				}
			} while (tempchar != '(');
			c++; // Move on to the next token
		}
		else if (operatorStack->Top == NULL)
		{
			// If operator Stack is empty, push token into stack
			// BUT THIS HAS TO BE DONE *AFTER* THE PREVIOUS COMPARISONS
			// so erroneous parentheses pairings are caught
			// No need to check for priority and all those comparisons
			PushToStack(operatorStack, *c);
			c++; // move on to next token
		}
		else
		{	
			// If operator Stack is NOT empty, check for token priority and select a case
			opriority = tokenpriority(operatorStack->Top->Data);

			// If token is an opening '(' or other grouping token, push into stack immediately
			if(opriority == 1)
			{
				PushToStack(operatorStack, *c);
				c++; // And move on
			}
			// If token is of less priority, we need to pop from stack until this condition
			// becomes false
			else if (cpriority < opriority)
			{
				// If incoming token has less priority than token at the top of the stack
				// pop from stack into destination string
				tempchar = PopFromStack(operatorStack);
				tempstr[0] = tempchar;
				strcat(dest, tempstr);
				// To compare again and again, DO NOT increment c
				// In otherwords, continue with loop but do not move on to the next token
			}
			else if (cpriority > opriority)
			{
				// If incoming token has greater priority than token at the top of the stack
				// push into stack
				PushToStack(operatorStack, *c);
				c++; // And move on
			}
			else if (cpriority == 5)
			{
				// If incoming token has equal priority w/ top of stack
				// 	If right associative (only ^ is right associative), push into stack)
				PushToStack(operatorStack, *c);
				c++; // And move on
			}		
			else // This case is executed if cpriority == opriority and token is left associative
			{
				// Else pop into destination string and compare again
				tempchar = PopFromStack(operatorStack);
				tempstr[0] = tempchar;
				strcat(dest, tempstr);
				// To compare again, DO NOT increment c;
				// Continue with loop but do not move on to the next token
			}
		}
	} while (*c != '\0');

	// Pop all remaining operators in the Stack; unless they are '('
	// For infix expressions completely bounded by a parenthesis pair,
	// But this is needed for expressions that do not begin and end with parentheses
	while(operatorStack->Top != NULL)
	{
		tempchar = PopFromStack(operatorStack);
		if (tempchar == '(')
		{
			// All '(' should have been popped in the previous loop
			// So, if there is still a '(' that means that at least one ')'
			// is missing; Report error
			char tempstr2[] = "Invalid Expression; Missing at least one ')' parenthesis.";
			strcpy(dest, tempstr2);
			AnnihilateStack(operatorStack);
			return NULL;
		}
		tempstr[0] = tempchar;
		strcat(dest, tempstr);
	}

	// clean up; free up stack and nodes
	AnnihilateStack(operatorStack);

	return dest;
}

//<summary>
// tokenpriority - takes in a character token and returns its priority
//</summary>
int tokenpriority(char token)
{
	switch(token)
	{
		// priority based on P-E-MD-AS order of precedence
		case '^':
			return 5;
		case '*':
		case '/':
			return 4;
		case '+':
		case '-':
			return 3;
		case ')':
			return 2;
		case '(':
			return 1;
		case ' ':
		case '\t':
			return -1;
		default:
		// If not an arithmetic operator, priority is returned as 0
			return 0;
	}
}

//<summary>
// findrank - returns true if the postfix expression is well-formed and false otherwise
//</summary>
bool findrank(char *str)
{
	int rank = 0; // Represents number of tokens in the stack
	do // Go through each character in the postfix expression
	{
		if (tokenpriority(*str) == 0)
		{
			rank++; // If token is an operand, increment rank (since 1 token would be pushed into the stack)
		}
		else
		{
			rank--; // If token is an operator, decrement rank (since 2 tokens would be popped and 1 pushed in)
		}
		str++;
	} while (*str != '\0' && rank >= 1); // End loop if rank is less than 1 (nothing in the stack)
	return (rank == 1) ? true : false;
}